﻿using System;
using System.Collections;

namespace Solution
{
    /// <summary>
    /// 最长回文子串
    /// </summary>
    public class Class1
    {
        /// <summary>
        /// 中心扩展法，子串为偶数时中心数为n-1，为奇数时为n，因此一共有2n-1个中心
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public string LongestPalindrome(string s)
        {
            if (s == null || s.Length < 1)
                return "";

            int start = 0;
            int end = 0;
            for (int i = 0; i < s.Length - 1; i++)
            {
                // 奇数
                int len1 = ExpandCenter(s, i, i);
                // 偶数
                int len2 = ExpandCenter(s, i, i + 1);
                int len = Math.Max(len1, len2);
                if (len > end - start + 1)
                {
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }

            return s.Substring(start, end - start + 1);
        }

        private int ExpandCenter(string s, int left, int right)
        {
            int l = left;
            int r = right;
            while (l >= 0 && r < s.Length && s[l] == s[r])
            {
                l--;
                r++;
            }
            return r - l - 1;
        }


        public string LongestPalindrome1(String s)
        {
            Stack stack = new Stack();
            /*
            几种基本类型：
            asddsa
            asdsa
            aaaaa
            aaaa
            */
            if (s.Length == 0 || s.Length == 1)
                return s;

            int maxLeft = -1;
            int maxRight = -1;
            int left = -1;
            int right = -1;
            bool isCombined = false;

            for (int i = 0; i < s.Length; i++)
            {

                if (stack.Count == 0)
                {
                    PosChar pc = new PosChar();
                    pc.c = s[i];
                    pc.pos = i;
                    stack.Push(pc);
                    continue;
                }

                if (((PosChar)stack.Peek()).c != s[i])
                {
                    PosChar pc = new PosChar();
                    pc.c = s[i];
                    pc.pos = i;
                    stack.Push(pc);

                    Compare(ref left, ref right, ref maxLeft, ref maxRight, isCombined);

                    left = -1;
                    right = -1;
                    isCombined = false;
                }

                else
                {
                    var tempPC = (PosChar)stack.Pop();
                    left = left == -1 ? tempPC.pos : left;
                    right = right > i ? right : i;

                    //maxLeft = maxLeft < left ? maxLeft : left;
                    //maxRight = maxRight > right ? maxRight : right;
                }
            }

            Compare(ref left, ref right, ref maxLeft, ref maxRight, isCombined);


            return s.Substring(maxLeft, maxRight - maxLeft + 1);
        }

        public void Compare(ref int left, ref int right, ref int maxLeft, ref int maxRight, bool isCombined)
        {
            if (right - left > maxRight - maxLeft)
            {
                maxLeft = left;
                maxRight = right;
            }
            //if (isCombined)
            //{
            //    if (right - maxLeft > maxRight - maxLeft)
            //    {
            //        maxLeft = left;
            //        maxRight = right;
            //    }
            //}
            //else
            //{
            //    if (right - left > maxRight - maxLeft)
            //    {
            //        maxLeft = left;
            //        maxRight = right;
            //    }
            //}
        }


        public struct PosChar
        {
            public int pos;
            public char c;
        }

    }
}
